In continuously operating, real-time systems, deallocation of system resources is an area where minor errors have major consequences. If errors occur in resource deallocation, or the system gets into an unusual state, resources are lost to processing and to the users of the system. Lost resources can cause delays, and in some cases, lead to system performance degradation or failure. Under current practice, the system programmer must carefully and thoroughly design and implement deallocation of memory resources.
This is a particularly critical problem in telephone switching systems databases, where access, allocation and deallocation of data base records occurs for each telephone call. Memory resources are used for each database record (herein "tuple") allocation. For purposes of this patent application, a "relation" is the definition of a record and a "tuple" is an instance of a relation. In other terms, a "relation" is a table and a "tuple" is a row of the table. Tuples must be recovered, otherwise memory resources will quickly become exhausted because the memory appears to the system to be full. Each program that recovers tuples therefore must allocate and deallocate these resources properly and carefully.
Programming practices that are used to recover resources carefully are complex and prior art solution to this problem are inadequate. In procedural program-controlled systems, audits are used to recover lost resources. Audits, however, are themselves complex to design and to implement properly, and require a substantial amount of system real-time to carry out their function. Further, audits have not yet been designed that can effectively handle all possible situations that may be encountered in continuously operating system. Initialization of part of all of the system is the only alternative in some cases, which can have severe impact on a switching system or other systems requiting long-term reliability.
Several program-controlled systems utilize a form of automatic storage management called "garbage collection," to recover memory resources. Generically, garbage collectors identify unreferenced data and return resources associated with identified unreferenced data to a pool of available resources. Most garbage collectors also include a form of memory compaction, which moves referenced data to substantially contiguous memory locations. A problem in the art is that most garbage collectors stop all other activity of the programming system for a significant, unpredictable duration of time, while the garbage collector is running, which makes them unsuitable for systems with real-time constraints.
A common garbage collector that stops all other activity while it is running is the mark/sweep garbage collector. In mark/sweep garbage collectors, the "mark" phase uses a set of root tuples as a basis for a recursive traversal of the graph of tuples referenced directly or indirectly by the root tuples, marking all tuples reachable from the root set. In the "sweep" phase, all tuples are sequentially examined. Tuples that are not marked are deleted and tuples that are marked are unmarked and saved. Obviously, the time required for the mark/sweep garbage collector to complete its task is at least proportional to the size of the system. For systems with real-time constraints, the uncontrolled time delay while the garbage collector runs is unacceptable.
A problem in the art, therefore, is that most garbage collectors are real-time intensive in that they block other processing from running while searching for unreferenced tuples and compressing data space.